package main.java.algorithms;

/**
 * @author Wrb
 * @date 2019/5/22 23:43
 */
public class MergeSort implements Sort {
	@Override
	//递归 自顶向上归并排序
	public void sort(int[] arr, int n) {
		sort(arr, 0, n - 1);
	}

	//非递归 自底向上归并排序
	public void sortBU(int arr[], int n) {
		for (int sz = 1; sz <= n; sz += sz) {
			for (int i = 0; i + sz < n; i += sz + sz) {
				merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));
			}
		}
	}

	//递归使用归并排序，对arr[l...r]的范围进行排序
	private void sort(int[] arr, int l, int r) {
//		if (l >= r) {
//			return;
//		}
		//优化2 当数组小到一定程度，插入排序比归并排序快，此时调用插入排序
		if (r - l <= 20) {
			InsertionSort.sort(arr, l, r);
			return;
		}
		//解决l+r的可能出现的溢出问题
		int mid = l + (r - l) / 2;
		sort(arr, l, mid);
		sort(arr, mid + 1, r);
		//优化1 当前半部分的最后一个值比后半部分的第一个值大时才需要进行归并排序
		if (arr[mid] > arr[mid + 1]) {
			merge(arr, l, mid, r);
		}
	}

	//将arr[l...mid]和arr[mid+1...r]两部分进行归并
	private void merge(int[] arr, int l, int mid, int r) {
		int aux[] = new int[r - l + 1];
		System.arraycopy(arr, l, aux, 0, r + 1 - l);
		int i = l, j = mid + 1;
		for (int k = l; k <= r; k++) {
			if (i > mid) {
				arr[k] = aux[j - l];
				j++;
			} else if (j > r) {
				arr[k] = aux[i - l];
				i++;
			} else if (aux[i - l] < aux[j - l]) {
				arr[k] = aux[i - l];
				i++;
			} else {
				arr[k] = aux[j - l];
				j++;
			}
		}
	}
}
